

import java.util.*;

public class contest_7_25 {

    public int getLucky(String s, int k) {
        String temp = "";
        for (int i = 0; i < s.length(); i++) {
            int dif = s.charAt(i) - 'a' + 1;
            temp += String.valueOf(dif);
        }
        for (int i = 0; i < k; i++) {
            long sum = 0;
            for (int j = 0; j < temp.length(); j++) {
                int dif = temp.charAt(j) - '0';
                sum += dif;
            }
            temp = String.valueOf(sum);
        }
        return Integer.valueOf(temp);
    }

    public String maximumNumber(String num, int[] change) {
        char[] chars = num.toCharArray();
        boolean flag = false;
        for (int i = 0; i < num.length(); i++) {
            int val = chars[i] - '0';
            if (change[val] > val) {
                chars[i] = (char) change[val];
                flag = true;
            } else if (change[val] < val) {
                if (flag) {
                    break;
                }
            }
        }
        return new String(chars);
    }

    int maxCompatibility = 0;

    public int maxCompatibilitySum(int[][] students, int[][] mentors) {
        int[][] scores = new int[students.length][mentors.length];

        for (int i = 0; i < students.length; i++) {
            for (int j = 0; j < mentors.length; j++) {
                int curScore = 0;
                for (int k = 0; k < students[0].length; k++) {
                    if (students[i][k] == mentors[j][k]) {
                        curScore++;
                    }
                }
                scores[i][j] = curScore;
            }
        }
        dfs(scores, 0, 0, new boolean[students.length]);
        return maxCompatibility;

    }

    private void dfs(int[][] scores, int start, int curSum, boolean[] used) {
        if (start == scores.length) {
            maxCompatibility = Math.max(maxCompatibility, curSum);
            return;
        }
        for (int i = 0; i < scores[0].length; i++) {
            if (!used[i]) {
                used[i] = true;
                curSum += scores[start][i];
                dfs(scores, start + 1, curSum, used);
                curSum -= scores[start][i];
                used[i] = false;
            }
        }
    }

    public String maximumTime(String time) {

        String hour = time.substring(0, 2);
        String min = time.substring(2);
        String tHour = "";
        String tMin = "";
        if (hour.equals("??")) {
            tHour = "23";
        } else if (hour.charAt(0) == '?') {
            int tail = Integer.valueOf(hour.charAt(1));
            for (int i = 0; i < 10; i++) {
                if (i * 10 + tail < 24) {
                    tHour = String.valueOf(i * 10 + tail);
                }
            }
        } else if (hour.charAt(1) == '?') {
            int head = Integer.valueOf(hour.charAt(0));
            for (int i = 0; i < 10; i++) {
                if (head * 10 + i < 24) {
                    tHour = String.valueOf(head * 10 + i);
                }
            }
        }

        if (min.equals("??")) {
            tMin = "59";

        } else if (min.charAt(0) == '?') {
            int tail = Integer.valueOf(min.charAt(1));
            for (int i = 0; i < 10; i++) {
                if (i * 10 + tail < 60) {
                    tMin = String.valueOf(i * 10 + tail);
                }
            }
        } else if (min.charAt(1) == '?') {
            int head = Integer.valueOf(min.charAt(0));
            for (int i = 0; i < 10; i++) {
                if (head * 10 + i < 60) {
                    tMin = String.valueOf(head * 10 + i);
                }
            }
        }
        return tHour + tMin;
    }


    public boolean isPrefixString(String s, String[] words) {

        int index = 0;
        for (int i = 0; i < words.length; i++) {
            int len = words[i].length();
            if (index + len > s.length()) {
                return false;
            }
            String sub = s.substring(index, index + len);
            if (!sub.equals(words[i])) {
                return false;
            }
            index += len;
            if (index == s.length()) {
                return true;
            }
        }
        return index == s.length();
    }

    public int minStoneSum(int[] piles, int k) {

        long sum = 0;
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> (b - a));
        for (int p :
                piles) {
            priorityQueue.offer(p);
            sum += p;
        }
        for (int i = 0; i < k; i++) {
            Integer max = priorityQueue.poll();
            int remove = (int) Math.floor(max / 2.0);
            sum -= remove;
            priorityQueue.offer(max - remove);
        }
        return (int) sum;

    }

    public int minSwaps(String s) {
        int left = 0;
        for (char c :
                s.toCharArray()) {
            if (c == '[') {
                left++;
            } else if (left != 0) {
                left--;
            }
        }
        return (left + 1) / 2;
    }

    public long numberOfWeeks(int[] milestones) {
        Arrays.sort(milestones);
        int res = 0;
        int left = 0, right = milestones.length - 1;
        while (left < right) {
            if (milestones[left] < milestones[right]) {
                milestones[right] -= milestones[left];
                res += milestones[left] * 2;
                left++;
            } else if (milestones[left] > milestones[right]) {
                milestones[left] -= milestones[right];
                res += milestones[right] * 2;
                right--;
            } else {
                right--;
                left++;
                res += milestones[left] + milestones[right];
            }
        }
        if (left == right) {
            return res + 1;
        }
        return res;
    }

    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            String s = strs[i];
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            map.computeIfAbsent(String.copyValueOf(chars), v -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(map.values());

    }

    public int numOfStrings(String[] patterns, String word) {

        int res = 0;
        for (int i = 0; i < patterns.length; i++) {
            for (int j = 0; j < word.length(); j++) {
                if (patterns[i].charAt(0) == word.charAt(j)) {
                    int len = patterns[i].length();
                    if (j + len > word.length()) {
                        break;
                    }
                    if (word.substring(j, j + len).equals(patterns[i])) {
                        res++;
                        break;
                    }
                }
            }
        }
        return res;
    }


    public int[] rearrangeArray(int[] nums) {

        Arrays.sort(nums);
        int index = 0;
        int[] res = new int[nums.length];
        for (int i = 0; i < res.length; i += 2) {
            res[i] = nums[index++];
        }
        for (int i = 1; i < res.length; i += 2) {
            res[i] = nums[index++];
        }
        return res;
    }

    public boolean isThree(int n) {
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (n % i == 0) {
                res++;
            }
            if (res > 3) {
                return false;
            }
        }
        return res == 3;

    }


    class NumArray {
        int[] preSum;

        public NumArray(int[] nums) {
            preSum = new int[nums.length + 1];
            for (int i = 0; i < nums.length; i++) {
                preSum[i + 1] = preSum[i] + nums[i];
            }
        }

        public int sumRange(int left, int right) {
            return preSum[right + 1] - preSum[left];
        }
    }


    public boolean checkRecord(String s) {
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i > 1) {
                if (s.charAt(i) == s.charAt(i - 1) && s.charAt(i - 1) == s.charAt(i - 2) && s.charAt(i) == 'L') {
                    return false;
                }
            }
            if (s.charAt(i) == 'A') {
                count++;
            }

        }
        return count < 2;

    }

    public int checkRecord(int n) {
        int[][][] memo = new int[n][2][3];
        return checkRecorddfs(0, n, 0, 0, memo);
    }

    private int checkRecorddfs(int day, int n, int absentDays, int lateDays, int[][][] memo) {

        if (day == n) {
            return 1;
        }
        if (memo[day][absentDays][lateDays] != 0) {
            return memo[day][absentDays][lateDays];
        }
        int ans = 0;
        ans = (ans + checkRecorddfs(day + 1, n, absentDays, 0, memo)) % 1000000007;
        if (absentDays < 2) {
            ans = (ans + checkRecorddfs(day + 1, n, 1, 0, memo)) % 1000000007;
        }
        if (lateDays < 3) {
            ans = (ans + checkRecorddfs(day + 1, n, absentDays, lateDays + 1, memo)) % 1000000007;
        }
        return memo[day][absentDays][lateDays] = ans;
    }

    private long helper(int n) {
        long res = 0;
        if (n < 3) {
            res = (long) Math.pow(2, n);
        } else {
            res = ((long) Math.pow(2, n) - (((long) (n - 1) * (n - 2))) / 2);
        }
        return res % 1000000007;
    }


    public int numDecodings(String s) {
        //1-26
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        dp[1] = s.charAt(0) == '0' ? 0 : 1;
        for (int i = 2; i <= s.length(); i++) {
            if (s.charAt(i - 1) != '0') {
                dp[i] = dp[i - 1];
            }
            int num = Integer.parseInt(s.substring(i - 2, i));
            if (num >= 10 && num < 27) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];

    }

    public boolean isValidSudoku(char[][] board) {
        boolean[][] rowCheck = new boolean[board.length][10];
        boolean[][] colCheck = new boolean[board[0].length][10];
        boolean[][] boxCheck = new boolean[9][10];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int num = c - '0';
                    if (rowCheck[i][num]) {
                        return false;
                    }
                    rowCheck[i][num] = true;
                    if (colCheck[j][num]) {
                        return false;
                    }
                    colCheck[j][num] = true;
                    if (boxCheck[(i / 3) * 3 + j / 3][num]) {
                        return false;
                    }
                    boxCheck[(i / 3) * 3 + j / 3][num] = true;
                }
            }
        }
        return true;
    }

    public void solveSudoku(char[][] board) {

        boolean[][] rowCheck = new boolean[board.length][10];
        boolean[][] colCheck = new boolean[board[0].length][10];
        boolean[][] boxCheck = new boolean[9][10];

        solveSudokudfs(rowCheck, colCheck, boxCheck, board);


    }

    private void solveSudokudfs(boolean[][] rowCheck, boolean[][] colCheck, boolean[][] boxCheck, char[][] board) {

    }

    public int findGCD(int[] nums) {
        Arrays.sort(nums);
        return maxDiv(nums[0], nums[nums.length - 1]);

    }

    private int maxDiv(int a, int b) {
        int min = Math.min(a, b);
        int res = 1;
        for (int i = 2; i <= min; i++) {
            if (a % i == 0 && b % i == 0) {
                res = i;
            }
        }
        return res;
    }

    public String findDifferentBinaryString(String[] nums) {

        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int num = 0;
            int t = 1;
            for (int j = nums[i].length() - 1; j >= 0; j--) {
                if (nums[i].charAt(j) != '0') {
                    num += t;
                }
                t *= 2;
            }

            set.add(num);
        }
        for (int i = 0; i < Math.pow(2, 16); i++) {
            if (!set.contains(i)) {
                String s = Integer.toBinaryString(i);
                if (s.length() < nums[0].length()) {
                    int dif = nums[0].length() - s.length();
                    for (int j = 0; j < dif; j++) {
                        s = "0" + s;
                    }
                }
                return s;
            }
        }
        return "";
    }

    int minRes = Integer.MAX_VALUE;

    public int minimizeTheDifference(int[][] mat, int target) {
        boolean[][] memo = new boolean[mat.length][5000];
        for (int j = 0; j < mat[0].length; j++) {
            memo[0][mat[0][j]] = true;
            minimizeTheDifferencedfs(1, mat, target, memo, mat[0][j]);
            if (minRes == 0) {
                return minRes;
            }
        }
        return minRes;
    }

    private void minimizeTheDifferencedfs(int row, int[][] mat, int target, boolean[][] memo, int temp) {
        if (row == mat.length) {
            minRes = Math.min(minRes, Math.abs(target - temp));
            return;
        }
        if (memo[row][temp]) {
            return;
        }
        memo[row][temp] = true;
        for (int j = 0; j < mat[0].length; j++) {

            minimizeTheDifferencedfs(row + 1, mat, target, memo, temp + mat[row][j]);
        }
    }

    public boolean findTarget(TreeNode root, int k) {
        List<Integer> list = new ArrayList<>();
        inOrder(root, list);
        int left = 0, right = list.size() - 1;
        while (left < right) {
            if (list.get(left) + list.get(right) == k) {
                return true;
            } else if (list.get(left) + list.get(right) > k) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }

    private void inOrder(TreeNode root, List<Integer> list) {

        if (root == null) {
            return;
        }
        inOrder(root.left, list);
        list.add(root.val);
        inOrder(root.right, list);
    }

//    public int getMaximumGenerated(int n) {
//        int max=0;
//        int [] nums=new int[n+1];
//        nums[1]=1;
//        for (int i = 2; i <=n; i++) {
//            if (i)
//        }
//
//    }

    public String complexNumberMultiply(String num1, String num2) {
        String[] split1 = num1.split("\\+");
        String[] split2 = num2.split("\\+");
        int num = Integer.parseInt(split1[0]) * Integer.parseInt(split2[0]) - Integer.parseInt(split1[1].substring(0, split1[1].length() - 1)) * Integer.parseInt(split2[1].substring(0, split2[1].length() - 1));
        int complex = Integer.parseInt(split1[0]) * Integer.parseInt(split2[1].substring(0, split2[1].length() - 1)) + Integer.parseInt(split2[0]) * Integer.parseInt(split1[1].substring(0, split1[1].length() - 1));
        return num + "+" + String.valueOf(complex) + "i";

    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> temp = new ArrayList<>();
        temp.add(0);
        allPathsSourceTargetdfs(graph, res, temp, 0);
        return res;

    }

    private void allPathsSourceTargetdfs(int[][] graph, List<List<Integer>> res, List<Integer> temp, int point) {
        if (point == graph.length) {
            res.add(new ArrayList<>(temp));
            return;
        }
        for (int i = 0; i < graph[point].length; i++) {
            temp.add(graph[point][i]);
            allPathsSourceTargetdfs(graph, res, temp, graph[point][i]);
            temp.remove(temp.size() - 1);
        }
    }


    public boolean isValidSerialization(String preorder) {

        String[] leaves = new String[preorder.length()];
        String[] split = preorder.split(",");
        int size = 0;
        for (int i = 0; i < split.length; i++) {
            leaves[size] = split[i];
            while (size >= 2 && leaves[size].equals(leaves[size - 1]) && leaves[size].equals("#") && !leaves[size - 2].equals("#")) {
                size -= 2;
                leaves[size] = "#";
            }
            size++;

        }
        if (size == 1 && leaves[size - 1].equals("#")) {
            return true;
        }
        return false;
    }

    public int minimumDifference(int[] nums, int k) {
        Arrays.sort(nums);
        int res = Integer.MAX_VALUE;
        for (int i = 0; i + k - 1 < nums.length; i++) {
            res = Math.min(res, nums[i + k - 1] - nums[i]);
        }
        return res;
    }

    public String kthLargestNumber(String[] nums, int k) {

        Arrays.sort(nums, (o1, o2) -> {
            if (o1.length() == o2.length()) {
                return o1.compareTo(o2);
            } else if (o1.length() < o2.length()) {
                return -1;
            } else {
                return 1;
            }
        });
        return nums[nums.length - k];
    }

    public int countQuadruplets(int[] nums) {
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                for (int k = j + 1; k < nums.length; k++) {
                    for (int l = k + 1; l < nums.length; l++) {
                        if (nums[i] + nums[j] + nums[k] == nums[l]) {
                            res++;
                        }
                    }
                }
            }
        }
        return res;

    }

    public int numberOfWeakCharacters(int[][] properties) {

        Arrays.sort(properties, (a, b) -> {
            if (a[0] == b[0]) {
                return Integer.compare(a[1], b[1]);
            }
            return Integer.compare(b[0], a[0]);
        });
        int max = 0;
        int res = 0;
        for (int i = 0; i < properties.length; i++) {
            if (properties[i][1] < max) {
                res++;
            }
            max = Math.max(max, properties[i][1]);
        }
        return res;
    }


    public String shiftingLetters(String s, int[] shifts) {
        int n = shifts.length;
        int[] pre = new int[n];
        pre[0] = shifts[0] % 26;
        for (int i = 1; i < n; i++) {
            pre[i] = (pre[i - 1] + shifts[i] % 26) % 26;
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            res.append((char) (s.charAt(i) + pre[i]));
        }
        return res.toString();
    }

    public String destCity(List<List<String>> paths) {
        Map<String, Integer> froms = new HashMap<>();
        Map<String, Integer> tos = new HashMap<>();
        for (List<String> p :
                paths) {
            froms.put(p.get(0), froms.getOrDefault(p.get(0), 0) + 1);
            tos.put(p.get(1), tos.getOrDefault(p.get(1), 0) + 1);
        }
        List<String> tosKeys = new ArrayList<>(tos.keySet());
        for (String to :
                tosKeys) {
            if (froms.containsKey(to)) {
                continue;
            } else {
                return to;
            }
        }
        return "";
    }

    public String fractionToDecimal(int numerator, int denominator) {

        long a = numerator, b = denominator;
        if (a % b == 0) {
            return String.valueOf(a / b);
        }
        StringBuilder res = new StringBuilder();
        if (a * b < 0) {
            res.append("-");
        }
        a = Math.abs(a);
        b = Math.abs(b);
        res.append(a / b).append(".");
        a %= b;
        Map<Long, Integer> map = new HashMap<>();
        while (a != 0) {
            map.put(a, res.length());
            a *= 10;
            res.append(a / b);
            a %= b;
            if (map.containsKey(a)) {
                int u = map.get(a);
                return String.format("%s(%s)", res.substring(0, u), res.substring(u));
            }
        }
        return res.toString();

    }


    public String licenseKeyFormatting(String s, int k) {
        StringBuilder sb = new StringBuilder();
        int pre = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            if (s.charAt(i) != '-') {
                sb.insert(0, Character.toUpperCase(s.charAt(i)));
            }
            if (sb.length() - pre == k) {
                sb.insert(0, '-');
                pre = sb.length();
            }

        }
        if (sb.length() > 0 && sb.charAt(0) == '-') {
            return sb.substring(1);
        }
        return sb.toString();
    }

    public int minimumMoves(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == 'X') {
                res++;
                i = i + 2;
            }

        }
        return res;

    }

    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> res = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != i + 1) {
                int supIdx = nums[i] - 1;
                if (nums[supIdx] == nums[i]) {
                    res.add(nums[i]);
                    continue;
                }
                int temp = nums[supIdx];
                nums[supIdx] = nums[i];
                nums[i] = temp;
                i--;
            }

        }
        return new ArrayList<>(res);

    }


    public int thirdMax(int[] nums) {
        long max = Long.MIN_VALUE, mid = Long.MIN_VALUE, res = Long.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= max) {
                res = mid;
                mid = max;
                max = nums[i];
            } else if (nums[i] >= mid) {
                res = mid;
                mid = nums[i];
            } else if (nums[i] >= res) {
                res = nums[i];
            }
        }
        if (res != Long.MIN_VALUE) {
            return (int) res;
        }
        return (int) max;
    }


    public int[] missingRolls(int[] rolls, int mean, int n) {
        int m = rolls.length;
        int sum = mean * (m + n) - Arrays.stream(rolls).sum();
        if (sum > n * 6 || sum < n) {
            return new int[0];
        }
        int[] res = new int[n];
        Arrays.fill(res, 1);
        sum -= n;
        for (int i = 0; i < n; i++) {
            if (sum - 5 > 0) {
                res[i] += 5;
                sum -= 5;
            } else {
                res[i] += sum;
                break;
            }
        }
        return res;

    }


    public int countSegments(String s) {
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i > 0 && s.charAt(i - 1) != ' ' && s.charAt(i) == ' ') {
                res++;
            } else if (i == s.length() - 1 && s.charAt(i) != ' ') {
                res++;
            }
        }
        return res;
    }


    public boolean exist(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (dfsExist2(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean dfsExist2(char[][] board, int i, int j, String word, int index) {
        if (index == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] != word.charAt(index)) {
            return false;
        }
        board[i][j] = '#';
        boolean res = dfsExist2(board, i + 1, j, word, index + 1) ||
                dfsExist2(board, i - 1, j, word, index + 1) ||
                dfsExist2(board, i, j + 1, word, index + 1) ||
                dfsExist2(board, i, j - 1, word, index + 1);
        board[i][j] = word.charAt(index);
        return res;
    }


    public List<String> findRepeatedDnaSequences(String s) {
        Map<String, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (i + 10 <= s.length()) {
                map.put(s.substring(i, i + 10), map.getOrDefault(s.substring(i, i + 10), 0) + 1);
            } else {
                break;
            }
        }
        List<String> res = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (entry.getValue() > 1) {
                res.add(entry.getKey());
            }
        }
        return res;
    }


    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (findWord(board, words[i])) {
                res.add(words[i]);
            }
        }
        return res;
    }

    private boolean findWord(char[][] board, String word) {
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (board[i][j] == word.charAt(0) && findWordDFS(board, i, j, word, 0)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean findWordDFS(char[][] board, int i, int j, String word, int index) {

        if (index == word.length()) {
            return true;
        }
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length || board[i][j] == '*' || board[i][j] != word.charAt(index)) {
            return false;
        }
        board[i][j] = '*';
        boolean res = findWordDFS(board, i + 1, j, word, index + 1) ||
                findWordDFS(board, i - 1, j, word, index + 1) ||
                findWordDFS(board, i, j + 1, word, index + 1) ||
                findWordDFS(board, i, j - 1, word, index + 1);
        board[i][j] = word.charAt(index);
        return res;
    }


    public int rangeBitwiseAnd(int left, int right) {
        int zero = 0;
        while (left != right) {
            left >>= 1;
            right >>= 1;
            zero++;
        }
        return left << zero;
    }


//    public int minOperations(int[][] grid, int x) {
//        if (x==1){
//            return
//        }
//
//    }


//    class SummaryRanges {
//
//        public SummaryRanges() {
//
//        }
//
//        public void addNum(int val) {
//
//        }
//
//        public int[][] getIntervals() {
//
//        }
//    }


    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        boolean isEnd = false;
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            TrieNode temp = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (temp.children[c - 'a'] == null) {
                    temp.children[c - 'a'] = new TrieNode();
                }
                temp = temp.children[c - 'a'];
            }
            temp.isEnd = true;
        }

        public boolean search(String word) {

            TrieNode temp = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (temp.children[c - 'a'] == null) {
                    return false;
                }
                temp = temp.children[c - 'a'];
            }
            return temp.isEnd;
        }

        public boolean startsWith(String prefix) {
            TrieNode temp = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (temp.children[c - 'a'] == null) {
                    return false;
                }
                temp = temp.children[c - 'a'];
            }
            return true;

        }
    }


    public List<Integer> twoOutOfThree(int[] nums1, int[] nums2, int[] nums3) {

        List<Integer> res = new ArrayList<>();
        int[] count = new int[101];
        boolean[] used = new boolean[101];

        for (int n1 :
                nums1) {
            if (!used[n1]) {
                used[n1] = true;
                count[n1]++;
            }
        }
        used = new boolean[101];
        for (int n2 :
                nums2) {
            if (!used[n2]) {

                used[n2] = true;
                count[n2]++;
            }
        }
        used = new boolean[101];
        for (int n3 :
                nums3) {
            if (!used[n3]) {
                used[n3] = true;
                count[n3]++;
            }
        }
        for (int i = 0; i < count.length; i++) {
            if (count[i] >= 2) {

                res.add(i);
            }
        }
        return res;
    }

    class StockPrice {
        PriorityQueue<Integer> minHeap;
        PriorityQueue<Integer> maxHeap;
        Map<Integer, Integer> sto;
        int curTS;

        public StockPrice() {

            minHeap = new PriorityQueue<>(Comparator.comparingInt(a -> a));
            maxHeap = new PriorityQueue<>((o1, o2) -> o2 - o1);
            sto = new HashMap<>();
            curTS = 0;
        }

        public void update(int timestamp, int price) {

            if (timestamp > curTS) {
                curTS = timestamp;
            }
            if (sto.containsKey(timestamp)) {
                int prePrice = sto.get(timestamp);
                minHeap.remove(prePrice);
                maxHeap.remove(prePrice);
            }
            minHeap.offer(price);
            maxHeap.offer(price);
            sto.put(timestamp, price);
        }

        public int current() {
            return sto.get(curTS);

        }

        public int maximum() {
            return maxHeap.peek();

        }

        public int minimum() {
            return minHeap.peek();

        }
    }


    public List<String> fizzBuzz(int n) {
        List<String> res = new ArrayList<>();
        for (int i = 1; i < n + 1; i++) {
            if (i % 3 == 0 && i % 5 == 0) {
                res.add("FizzBuzz");
            } else if (i % 3 == 0) {
                res.add("Fizz");
            } else if (i % 5 == 0) {
                res.add("Buzz");
            } else {
                res.add(String.valueOf(i));
            }
        }
        return res;

    }

    public TreeNode bstFromPreorder(int[] preorder) {
        if (preorder.length < 1) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[0]);
        for (int i = 1; i < preorder.length; i++) {
            insertBST(preorder[i], root);
        }
        return root;

    }

    private TreeNode insertBST(int val, TreeNode node) {
        if (node == null) {
            return new TreeNode(val);
        }
        if (val > node.val) {
            node.right = insertBST(val, node.right);
        } else {
            node.left = insertBST(val, node.left);
        }
        return node;
    }

    public int numSquares(int n) {
        int[] dp = new int[n + 1];
        //dp[i] 表示到i需要最少的数量
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];

    }

    public int maxProfit(int[] prices) {
        if (prices.length < 2) {
            return 0;
        }
        int[] buy = new int[prices.length];
        int[] sell = new int[prices.length];

        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            if (i == 1) {
                buy[i] = Math.max(-prices[i], buy[i - 1]);
                sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
            } else {
                buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);
                sell[i] = Math.max(buy[i - 1] + prices[i], sell[i - 1]);
            }
        }
        return sell[prices.length - 1];
    }

    public boolean areNumbersAscending(String s) {

        int pre = 0;
        String[] s1 = s.split(" ");
        for (int i = 0; i < s1.length; i++) {
            if (Character.isDigit(s1[i].charAt(0))) {
                int temp = Integer.parseInt(s1[i]);
                if (temp > pre) {
                    pre = temp;
                } else {
                    return false;
                }
            }
        }
        return true;

    }

    class Bank {

        long[] balance;

        public Bank(long[] balance) {
            this.balance = new long[balance.length];
            for (int i = 0; i < balance.length; i++) {
                this.balance[i] = balance[i];
            }
        }

        public boolean transfer(int account1, int account2, long money) {
            account1--;
            account2--;
            if (account1 >= balance.length || account2 >= balance.length || balance[account1] < money) {
                return false;
            }
            balance[account1] -= money;
            balance[account2] += money;
            return true;
        }

        public boolean deposit(int account, long money) {
            account--;
            if (account >= balance.length) {
                return false;
            }
            balance[account] += money;
            return true;

        }

        public boolean withdraw(int account, long money) {
            account--;
            if (account >= balance.length) {
                return false;
            }
            if (money > balance[account]) {
                return false;
            }
            balance[account] -= money;
            return true;
        }
    }

    Map<Integer, Integer> count = new HashMap<>();
    int max = 0;

    public int countMaxOrSubsets(int[] nums) {
        countMaxOrSubsetsDFS(nums, 0, 0);
        return count.get(max);
    }

    private void countMaxOrSubsetsDFS(int[] nums, int start, int temp) {
        if (start > nums.length) {
            return;
        }
        max = Math.max(max, temp);
        count.put(temp, count.getOrDefault(temp, 0) + 1);
        for (int i = start; i < nums.length; i++) {
            countMaxOrSubsetsDFS(nums, i + 1, temp | nums[i]);
        }
    }

    int pathCount = 0;

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            pathSumDFS(node, targetSum);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return pathCount;
    }

    private void pathSumDFS(TreeNode root, int targetSum) {
        if (root == null) {
            return;
        }
        targetSum -= root.val;
        if (targetSum == 0) {
            pathCount++;
        }
        pathSumDFS(root.left, targetSum);
        pathSumDFS(root.right, targetSum);
    }

    public int kthSmallest(TreeNode root, int k) {
        List<TreeNode> list = new ArrayList<>(k);
        kthSmallestdfs(list, root, k);
        return list.get(k - 1).val;

    }

    public boolean isCousins(TreeNode root, int x, int y) {
        {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                int size = queue.size();
                int count = 0;
                for (int i = 0; i < size; i++) {
                    TreeNode node = queue.poll();
                    if (node.left != null) {
                        if (node.left.val == x || node.left.val == y) {
                            count++;
                        }
                        queue.offer(node.left);
                    }
                    if (node.right != null) {
                        if (node.right.val == x || node.right.val == y) {
                            count++;
                        }
                        queue.offer(node.right);
                    }
                    if (node.left != null && node.right != null) {
                        if (node.left.val == x && node.right.val == y || node.left.val == y && node.right.val == x) {
                            return false;
                        }
                    }

                    if (count == 2) {

                        return true;
                    }

                }

            }

        }
        return false;
    }


    private void kthSmallestdfs(List<TreeNode> list, TreeNode root, int k) {
        if (root == null) {
            return;
        }
        kthSmallestdfs(list, root.left, k);
        if (list.size() < k) {
            list.add(root);
        }
        kthSmallestdfs(list, root.right, k);
    }

    public int findComplement(int num) {
        int highbit = 0;
        for (int i = 1; i < 31; i++) {
            if (num >= (1 << i)) {
                highbit = i;
            } else {
                break;
            }
        }
        int mask = highbit == 30 ? 0x7fffffff : (1 << (highbit + 1)) - 1;
        return num ^ mask;

    }


    class WordDictionary {
        Map<Integer, List<String>> map;

        public WordDictionary() {
            map = new HashMap<>();

        }

        public void addWord(String word) {
            map.computeIfAbsent(word.length(), v -> new ArrayList<>()).add(word);
        }

        public boolean search(String word) {
            if (!map.containsKey(word.length())) {
                return false;
            }

            List<String> candi = map.get(word.length());
            for (int i = 0; i < candi.size(); i++) {
                if (isSame(candi.get(i), word)) {
                    return true;
                }
            }
            return false;
        }

        private boolean isSame(String s, String word) {
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == word.charAt(i) || word.charAt(i) == '.') {
                } else {
                    return false;
                }
            }
            return true;
        }
    }


    public String reverseWords(String s) {

        StringBuilder res = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            StringBuilder t = new StringBuilder();
            int j = i;
            while (j < s.length() && s.charAt(j) != ' ') {
                t.append(s.charAt(j));
                j++;
            }
            if (j != i) {
                res.insert(0, t);
                res.insert(0, " ");

            }
            i = j;

        }
        return res.substring(1);
    }

    public int minMoves(int[] nums) {
        int min = Arrays.stream(nums).min().getAsInt();
        int res = 0;
        for (int i = 0; i < nums.length; i++) {
            res += (nums[i] - min);
        }
        return res;
    }


    static class RandomizedSet {
        Map<Integer, Integer> map;
        List<Integer> list;
        int tailIdx;

        public RandomizedSet() {

            tailIdx = -1;
            map = new HashMap<>();
            list = new ArrayList<>();
        }

        public boolean insert(int val) {
            if (map.containsKey(val)) {
                return false;
            }
            tailIdx++;
            list.add(val);
            map.put(val, tailIdx);
            return true;
        }

        public boolean remove(int val) {
            if (!map.containsKey(val)) {
                return false;
            }
            int index = map.get(val);
            int lastEle = list.get(tailIdx);
            int lastEleIdx = map.get(lastEle);
            list.set(index, lastEle);
            list.set(lastEleIdx, val);
            list.remove(tailIdx);
            tailIdx--;
            map.put(lastEle, index);
            map.remove(val);
            return true;
        }

        public int getRandom() {
            Random random = new Random();
            int i = random.nextInt(tailIdx + 1);
            return list.get(i);

        }
    }


    public int[] plusOne(int[] digits) {

        int carry = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            int sum = carry + digits[i];
            digits[i] = sum % 10;
            carry = sum / 10;
        }
        if (carry != 0) {
            int[] res = new int[digits.length + 1];
            res[0] = carry;
            for (int i = 1; i < res.length; i++) {
                res[i] = digits[i - 1];
            }
            return res;

        }
        return digits;
    }

    public String frequencySort(String s) {

        Map<Character, StringBuilder> map = new HashMap<>();
        for (char c : s.toCharArray()) {
            map.put(c, map.getOrDefault(c, new StringBuilder()).append(c));
        }
        List<Map.Entry<Character, StringBuilder>> list = new ArrayList<>(map.entrySet());
        Collections.sort(list, (a, b) -> (b.getValue().length() - a.getValue().length()));
        StringBuilder res = new StringBuilder();
        for (Map.Entry<Character, StringBuilder> entry : list) {
            res.append(entry.getValue());
        }
        return res.toString();
    }

    public List<Integer> majorityElement(int[] nums) {

        List<Integer> ans = new ArrayList<>();
        int stan = (int) Math.floor(nums.length / 3.0);
        Map<Integer, Integer> res = new HashMap<>();
        for (int n : nums) {
            res.put(n, res.getOrDefault(n, 0) + 1);
        }
        for (Map.Entry<Integer, Integer> entry : res.entrySet()) {
            if (entry.getValue() > stan) {
                ans.add(entry.getKey());
            }
        }
        return ans;
    }

    public int uniquePathsIII(int[][] grid) {

        return 0;

    }

    public int numTrees(int n) {

        int[] dp=new int[n+1];
        dp[0]=dp[1]=1;
        for (int i = 2; i < n + 1; i++) {
            for (int j = 0; j <i/2; j++) {
                dp[i]+=2*dp[j]*dp[i-1-j];
            }
            if (i%2!=0){
                dp[i]+=dp[i/2]*dp[i/2];
            }
        }
        return dp[n];
    }


    public int[] constructRectangle(int area) {
        int resW = 1;
        for (int w = 1; w <= Math.sqrt(area); w++) {
            if (area % w == 0) {
                resW = w;
            }
        }
        return new int[]{area / resW, resW};
    }

    public int countValidWords(String sentence) {

        int res = 0;
        String[] splits = sentence.split(" ");
        for (String s : splits) {
            if (s.length() == 0) {
                continue;
            }
            int count1 = 0;
            int count2 = 0;
            boolean flag = true;
            for (int i = 0; i < s.length(); i++) {
                if (Character.isDigit(s.charAt(i))) {
                    flag = false;
                    break;
                } else if (s.charAt(i) == '-') {
                    if (i - 1 >= 0 && Character.isAlphabetic(s.charAt(i - 1)) && i + 1 < s.length() && Character.isAlphabetic(s.charAt(i + 1))) {
                        if (count1 == 1) {
                            flag = false;
                            break;
                        }
                        count1++;
                    } else {
                        flag = false;
                        break;
                    }
                } else if (Character.isAlphabetic(s.charAt(i))) {
                } else {
                    if (i == s.length() - 1) {
                        if (count2 == 1) {
                            flag = false;
                            break;
                        }
                        count2++;
                    } else {
                        flag = false;
                        break;
                    }
                }
            }
            if (flag) {
                res++;
            }
        }
        return res;
    }

    public int shoppingOffers(List<Integer> price, List<List<Integer>> special, List<Integer> needs) {
        return shoppingOffersHelper(price, special, 0, needs);
    }

    private int shoppingOffersHelper(List<Integer> price, List<List<Integer>> special, int index, List<Integer> needs) {
        int local_min = perchase(needs, price);
        for (int j = 0; j < special.size(); j++) {
            List<Integer> sp = special.get(j);
            List<Integer> temp = new ArrayList<>();
            for (int i = 0; i < needs.size(); i++) {
                if (needs.get(i) < sp.get(i)) {
                    temp = null;
                    break;
                }
                temp.add(needs.get(i) - sp.get(i));
            }
            if (temp != null) {
                local_min = Math.min(local_min, sp.get(needs.size()) + shoppingOffersHelper(price, special, j, temp));
            }
        }
        return local_min;

    }

    private int perchase(List<Integer> needs, List<Integer> price) {
        int res = 0;
        for (int i = 0; i < needs.size(); i++) {
            res += needs.get(i) * price.get(i);
        }
        return res;
    }


    public int countNodes(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) {
            return 0;
        }
        queue.offer(root);
        int times = 0;
        int res = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            if (size != Math.pow(2, times)) {
                return res + size;
            }
            res += size;
            times++;
            for (int i = 0; i < size; i++) {

                TreeNode poll = queue.poll();
                if (poll.left != null) {
                    queue.offer(poll.left);
                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }

            }

        }
        return res;

    }

    public boolean searchMatrix(int[][] matrix, int target) {

        int i = 0, j = matrix[0].length - 1;
        while (i < matrix.length && j >= 0) {
            if (matrix[i][j] == target) {
                return true;
            } else if (matrix[i][j] < target) {
                i++;
            } else {
                j--;
            }
        }
        return false;
    }


    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        TreeNode left = invertTree(root.left);
        TreeNode right = invertTree(root.right);
        root.left = right;
        root.right = left;
        return root;

    }


    class MinStack {
        Stack<int[]> stack;

        public MinStack() {
            stack = new Stack<>();

        }

        public void push(int val) {
            if (stack.isEmpty()) {
                stack.push(new int[]{val, val});
            } else {
                int min = stack.peek()[1];
                stack.push(new int[]{val, Math.min(min, val)});
            }

        }

        public void pop() {
            stack.pop();

        }

        public int top() {

            return stack.peek()[0];
        }

        public int getMin() {

            return stack.peek()[1];
        }

    }

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Stack<Integer> minStack = new Stack<>();
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = nums2.length - 1; i >= 0; i--) {
            while (!minStack.isEmpty() && minStack.peek() < nums2[i]) {
                minStack.pop();
            }
            map.put(nums2[i], minStack.isEmpty() ? -1 : minStack.peek());
            minStack.push(nums2[i]);

        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < res.length; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;

    }

    public boolean reorderedPowerOf2(int n) {
        int[] count = new int[10];
        String s = String.valueOf(n);
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - '0']++;
        }

        for (int i = 0; Math.pow(2, i) <= 1000000000; i++) {
            int value = (int) Math.pow(2, i);
            int[] temp = new int[10];
            String ss = String.valueOf(value);
            for (int j = 0; j < ss.length(); j++) {
                temp[ss.charAt(j) - '0']++;
            }
            boolean flag = false;
            for (int j = 0; j < 10; j++) {
                if (count[j] != temp[j]) {
                    flag = true;
                    break;
                }
            }
            if (!flag) {
                return true;
            }
        }
        return false;
    }

    public List<List<Integer>> threeSum(int[] nums) {
        Set<List<Integer>> res = new HashSet<>();
        Arrays.sort(nums);
        for (int i = 0; i < nums.length - 2; i++) {

            int start = i + 1, end = nums.length - 1;
            while (start < end) {

                if (nums[start] + nums[end] == -nums[i]) {
                    res.add(Arrays.asList(nums[i], nums[start], nums[end]));
                    start++;
                    while (start < end && nums[start] == nums[start - 1]) {
                        start++;
                    }
                    end--;
                    while (start < end && end + 1 < nums.length && nums[end] == nums[end + 1]) {
                        end--;
                    }

                } else if (nums[start] + nums[end] < -nums[i]) {
                    start++;
                } else {
                    end--;
                }


            }
        }
        return new ArrayList<>(res);

    }

    public String kthDistinct(String[] arr, int k) {
        Map<String, Integer> map = new HashMap<>();
        for (String s : arr) {
            map.put(s, map.getOrDefault(s, 0) + 1);
        }
        for (String s : arr) {
            if (map.get(s) == 1) {
                k--;
            }
            if (k == 0) {
                return s;
            }
        }
        return "";

    }

    public int maxTwoEvents(int[][] events) {
        int res = 0;
        Arrays.sort(events, Comparator.comparingInt(a -> a[0]));
        int max = 0;
        PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        for (int[] event : events) {
            while (!priorityQueue.isEmpty() && priorityQueue.peek()[1] < event[0]) {
                max = Math.max(max, priorityQueue.poll()[2]);
            }
            res = Math.max(res, max + event[2]);
            priorityQueue.offer(event);
        }
        return res;

    }

    public int distributeCandies(int[] candyType) {

        int n = candyType.length;
        Map<Integer, Integer> map = new HashMap<>();
        for (int c : candyType) {
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        if (n / 2 <= map.size()) {
            return n / 2;
        }
        return map.size();
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    public void deleteNode(ListNode node) {

        while (node.next.next != null) {
            node.val = node.next.val;
            node = node.next;
        }
        ListNode pre = node;
        pre.val = node.next.val;
        pre.next = null;
    }


    public boolean isPerfectSquare(int num) {
        double x0 = num;
        while (true) {
            double x1 = (x0 + num / x0) / 2.0;
            if (x0 - x1 < 1e-6) {
                break;
            }
            x0 = x1;
        }
        int x = (int) x0;
        return x * x == num;

    }


    public int sumOfLeftLeaves(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int temp = 0;
        if (root.left != null && root.left.left == null && root.left.right == null) {
            temp += root.left.val;
        }
        return temp + sumOfLeftLeaves(root.left) + sumOfLeftLeaves(root.right);
    }

    public int[] singleNumber(int[] nums) {

        int xor = 0;
        for (int num : nums) {
            xor ^= num;
        }
        int mask = 1;
        while ((mask & xor) == 0) {
            mask *= 2;
        }
        int xor1 = 0;
        for (int num : nums) {
            if ((num & mask) == 0) {
                xor1 ^= num;
            }
        }
        return new int[]{xor1, xor ^ xor1};
    }


    public int sumNumbers(TreeNode root) {
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int res=0;
        Queue<Integer> layer=new LinkedList<>();
        layer.offer(root.val);
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                Integer val = layer.poll();
                if (node.left==null&&node.right==null){
                    res+=val;
                    continue;
                }
                if (node.left!=null){
                    queue.offer(node.left);
                    layer.offer(val*10+node.left.val);
                }
                if (node.right!=null){
                    queue.offer(node.right);
                    layer.offer(val*10+node.right.val);
                }
            }

        }
        return res;
    }


    public int missingNumber(int[] nums) {

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] - 1 != i) {

            }
        }
        return 0;

    }


    public int arrangeCoins(int n) {
        return (int) (Math.sqrt(2 * (long) n + 0.25) - 0.5); // cast "n" to "long" to avoid integer overflow
    }

    public int longestSubsequence(int[] arr, int difference) {
        Map<Integer, Integer> map = new HashMap<>();
        int res = 0;
        for (int a : arr) {
            if (!map.containsKey(a - difference)) {
                map.put(a, 1);
            } else {
                map.put(a, map.get(a - difference) + 1);
            }
            res = Math.max(res, map.get(a));
        }
        return res;
    }


    public int countVowelSubstrings(String word) {
        int res = 0;
        for (int i = 0; i < word.length(); i++) {
            Map<Character, Integer> map = new HashMap<>();
            for (int j = i; j < word.length(); j++) {
                char c = word.charAt(j);
                if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                    map.put(c, map.getOrDefault(c, 0) + 1);
                    if (map.size() >= 5) {
                        res++;
                    }
                } else {
                    break;
                }
            }
        }
        return res;
    }


    public long countVowels(String word) {

        long[] dp = new long[word.length() + 1];
        Set<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        long res = 0;
        for (int i = 1; i < word.length() + 1; i++) {
            if (set.contains(word.charAt(i - 1))) {
                dp[i] = dp[i - 1] + i;
            } else {
                dp[i] = dp[i - 1];
            }
            res += dp[i];
        }
        return res;
    }

    public int maxCount(int m, int n, int[][] ops) {
        int minX = m;
        int minY = n;
        for (int[] o : ops) {
            minX = Math.min(o[0], minX);
            minY = Math.min(o[1], minY);
        }
        return minX * minY;

    }

    public String multiply(String num1, String num2) {
        int[] res=new int[num1.length()+num2.length()];
        num1=new StringBuffer(num1).reverse().toString();
        num2=new StringBuilder(num2).reverse().toString();
        for (int i = 0; i < num1.length(); i++) {
            int carry=0;
            for (int j = 0; j < num2.length(); j++) {
                int temp=(num1.charAt(i)-'0')*(num2.charAt(j)-'0')+carry+res[i+j];
                res[i+j]=temp%10;
                carry=temp/10;
            }
            if (carry!=0){
                res[i+ num2.length()]+=carry;
            }
        }
        StringBuilder stringBuilder=new StringBuilder();
        for (int i = 0; i < res.length; i++) {
            stringBuilder.insert(0,res[i]);
        }

        for (int i = 0; i < stringBuilder.length(); i++) {
            if (stringBuilder.charAt(i)!='0'){
                return stringBuilder.substring(i);
            }
        }
        return "0";
    }


    public String getHint(String secret, String guess) {
        int A=0,B=0;
        Map<Character,List<Integer>> mapSecret=new HashMap<>();
        Map<Character,List<Integer>> mapGuess=new HashMap<>();
        for (int i = 0; i < secret.length(); i++) {
            if (secret.charAt(i)==guess.charAt(i)){
                A++;
            }else {
                mapSecret.computeIfAbsent(secret.charAt(i),v->new ArrayList<>()).add(i);
                mapGuess.computeIfAbsent(guess.charAt(i),v->new ArrayList<>()).add(i);
            }
        }
        for(Map.Entry<Character,List<Integer>> entry:mapSecret.entrySet()){
            if (mapGuess.containsKey(entry.getKey())) {
                B += Math.min(entry.getValue().size(), mapGuess.get(entry.getKey()).size());
            }
        }
        return A+"A"+B+"B";
    }

    public static void main(String[] args) {
        contest_7_25 contest_7_25 = new contest_7_25();

        System.out.println(contest_7_25.getHint("1123","0111"));
        System.out.println(contest_7_25.multiply("123","456"));

        System.out.println(contest_7_25.maxCount(3, 3, new int[][]{}));
        System.out.println(contest_7_25.countVowels("aba"));
        System.out.println(contest_7_25.countVowelSubstrings("duuebuaeeeeeeuaoeiueaoui"));


        System.out.println(contest_7_25.longestSubsequence(new int[]{1, 5, 7, 8, 5, 3, 4, 2, 1}, -2));
        System.out.println(contest_7_25.singleNumber(new int[]{1, 2, 1, 3, 2, 5}));
        System.out.println(contest_7_25.maxTwoEvents(new int[][]{{1, 3, 2}, {4, 5, 2}, {2, 4, 3}}));

        System.out.println(contest_7_25.threeSum(new int[]{-1, 0, 1, 2, -1, -4}));


        System.out.println(contest_7_25.countValidWords("he bought 2 pencils, 3 erasers, and 1  pencil-sharpener."));

        System.out.println(contest_7_25.reverseWords("i  sdf si "));

        System.out.println(contest_7_25.findComplement(5));
        System.out.println(contest_7_25.numSquares(13));


        System.out.println(contest_7_25.bstFromPreorder(new int[]{8, 5, 1, 7, 10, 12}));

        System.out.println(contest_7_25.countSegments(""));

        System.out.println(contest_7_25.thirdMax(new int[]{2, 2, 3, 1}));
        System.out.println(contest_7_25.groupAnagrams(new String[]{"eat", "tea", "tan", "ate", "nat", "bat"}));
        System.out.println(contest_7_25.maximumNumber("214010",
                new int[]{6, 7, 9, 7, 4, 0, 3, 4, 4, 7}));
        System.out.println(Integer.MAX_VALUE);
        System.out.println(contest_7_25.findDifferentBinaryString(new String[]{"00", "01"}));
        System.out.println(contest_7_25.minimizeTheDifference(new int[][]{{10, 3, 7, 7, 9, 6, 9, 8, 9, 5}, {1, 1, 6, 8, 6, 7, 7, 9, 3, 9}, {3, 4, 4, 1, 3, 6, 3, 3, 9, 9}, {6, 9, 9, 3, 8, 7, 9, 6, 10, 6}
        }, 5));
        System.out.println(contest_7_25.complexNumberMultiply("1+1i", "1+1i"));
        System.out.println(contest_7_25.shiftingLetters("abc", new int[]{3, 5, 9}));

    }
}

